package com.dyb.demo.algorithm;

import java.util.Arrays;

/**
 * @author dyb
 * @Description 二叉堆排序
 * @date 2019/3/2 14:52
 */
public class HeapOperator {

    /**
     * 上浮调整
     * 只有是完全二叉树的时候结果才是正确的
     *
     * @param array 待调整的堆
     */
    public static void upAdjust(int[] array) {
        int tag = array.length / 2 + 1;
        for (int i = 1; i <= tag; i++) {
            int childIndex = array.length - i;
            // 父节点下标为pi，则左右子节点下标为 2*pi+1 、2*pi+2
            // 可能没有右节点，所以 减1
            int parentIndex = (childIndex - 1) / 2;
            // temp保存插入的叶子节点值，用于最后的赋值
            int temp = array[childIndex];
            while (childIndex > 0 && temp < array[parentIndex]) {
                // 无需真正交换，单向赋值即可
                array[childIndex] = array[parentIndex];
                childIndex = parentIndex;
                parentIndex = (parentIndex - 1) / 2;
            }
            array[childIndex] = temp;
        }
    }

    /**
     * 下沉调整
     * 思路：1.先定位到最后一个非叶子节点，然后和其最小的子节点比较，如果子节点较小则进行交换，使最小值的节点上浮。
     * 2. 如果节点发生交换，还需要判断交换下沉节点的孩子节点是否有比其小的值，有则继续上浮。
     *
     * @param array       待调整的堆
     * @param parentIndex 要下沉的父节点
     * @param parentIndex 堆的有效大小
     */
    public static void downAdjust(int[] array, int parentIndex, int length) {
        // temp保存父节点值，用于最后的赋值
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            // 如果父节点小于任何一个孩子的值，直接跳出
            if (temp <= array[childIndex]) break;
            // 无需真正交换，单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 构建堆
     *
     * @param array 待调整的堆
     */
    public static void buildHeap(int[] array) {
        // 从最后一个非叶子节点开始，依次下沉调整
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{1, 7, 9, 3, 6, 8, 10, 2, 4, 0, 2};
        upAdjust(array);
//		System.out.println(Arrays.toString(array));

        array = new int[]{7, 6, 3, 10, 5, 2, 8, 9, 1};
        buildHeap(array);
        System.out.println(Arrays.toString(array));
    }
}
